package org.example.myleet.p754;

public class Solution {
    public int reachNumber(int target) {
        //由于左右走向是可以反过来的，因此负数部分可以按正数部分一样操作，因此忽略负数部分
        target = Math.abs(target);
        //需要到达target，那么至少1叫到n的和大于等于target，使用普通的等差数列求和公式
        int i = 1;
        long sum = (1 + i) * i / 2;
        while (sum < target) {
            ++i;
            sum = (long) (1 + i) * i / 2;
        }
        if (sum - target == 0) {
            //如果sum刚好等于target，那么一定是最少步数，得到结果
            return i;
        }
        long delta = sum - target;
        if ((delta & 1) == 0) {
            //如果差值是偶数，则一定可以通过挑选部分数字进行向左运动（减掉）以获得target
            return i;
        }
        //如果差值是奇数，则要么是i+1的结果，要么是i+2的结果，取决于哪一个可以使差值为偶数
        ++i;
        delta = (long) (1 + i) * i / 2 - target;
        if ((delta & 1) == 0) {
            return i;
        }
        return ++i;
    }
}
